package cn.cxq.learning.array;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;

/**
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：463859
 * 本题知识点： 穷举
 * 算法知识视频讲解
 * 题目描述
 * 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
 * 返回值描述:
 * 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
 * 示例1
 * 输入
 * 复制
 * 9
 * 返回值
 * 复制
 * [[2,3,4],[4,5]]
 */
public class ContinuousSequence {

    @Test
    public void testFindContinuousSequence() {
        System.out.println(FindContinuousSequence(2));
    }

    //利用求和公式来简化程序逻辑
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();

        if (sum == 0 || sum == 1) {
            return result;
        }

        int index = 2;

        while ((1 + (index + 1)) * (index + 1) / 2 <= sum) {
            index++;
        }

        while (index > 1) {
            int temp = sum - (1 + index) * index / 2;//减去和之后的差
            if (temp / index * index == temp) {  //看看差除以index是否除得尽
                //求中间结果
                ArrayList<Integer> middleResult = new ArrayList<>();
                for (int i = 1; i <= index; i++) {
                    middleResult.add(i + temp / index);
                }
                //将中间件结果存入结果数组中
                result.add(middleResult);
            }
            index--;
        }

        return result;
    }
}
